%%% Copyright 2010 Google Inc.
%%%
%%% Licensed under the Apache License, Version 2.0 (the "License");
%%% you may not use this file except in compliance with the License.
%%% You may obtain a copy of the License at
%%%
%%%     http://www.apache.org/licenses/LICENSE-2.0
%%%
%%% Unless required by applicable law or agreed to in writing, software
%%% distributed under the License is distributed on an "AS IS" BASIS,
%%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%%% See the License for the specific language governing permissions and
%%% limitations under the License.

%%% @copyright 2010 Google Inc. All Rights Reserved.
%%% @author <jacoby@google.com> Jacoby Thwaites [http://sites/madcloud]
%%% @version {@version}
%%% @doc
%%% Builds the labelled digraph used for sequencing. This is done by adding
%%% items to an agenda queue, and processing agenda items repeatedly until done.
%%%
%%% Each agenda item corresponds to an output set of an operation. The
%%% different types of op determine its role in generating vertices, edges
%%% and their labels.
%%%
%%% The operation types are described in the txm.hrl header file. The ones
%%% we use in this module are:
%%% <ul>
%%% <li>`N' - Notification (output only). Used to generate the initial
%%%           agenda items, which result in a vertex per output set.</li>
%%% <li>'OO' - One-way (input only). Referenced in the `vertex_label' record
%%%            of all vertices that can satisfy the OO consumer.</li>
%%% <li>`RR' - Request/Reply (non-intersecting input and output).
%%%            These ops generate edges from one vertex to another. Each edge
%%%            is labelled with the RR op that generated it using the
%%%            `edge_label' record.</li>
%%% <li>`IRR' - Iterative Request/Reply (intersecting input and output).
%%%             These ops are referenced as consumers like OO ops, and
%%%             as producers of vertices like N ops.</li>
%%% </ul>
%%%
%%% The digraph vertices and edges are labelled with a vertex_label and
%%% edge_label record respectively. There is one vertex per state fieldset,
%%% and one or more edges joining vertices where each edge is labelled with
%%% a single RR op id.
%%%
%%% If more than one RR op leads from one vertex to another, then each op
%%% generates a separate edge.
%%%
%%% @headerfile "../include/txm.hrl"
%%% @headerfile "../include/graph.hrl"

-module(graph).

-include("txm.hrl").
-include("graph.hrl").

-export([graph/1, get_vertex/2]).

%% @doc Constructs and returns a digraph from the composition of `FolderSpec'.
%% The agenda is initialized with the outputs of all N ops in the composition.
%% `Db' contains the digraph, agenda and used vertex sets, and is
%% updated as the agenda items are processed.
%% `Ops' is the static set of RR, IRR and OO ops against which the Db
%% is updated.
%% @spec graph(ref()) -> {digraph(), ets(), list()}
graph(FolderRef) ->

  % Create a db comprising digraph, agenda and used vertex list.
  Db = {Graph = digraph:new([acyclic]),

        % The agenda is in order of insertion. It's a queue
        % whose first element is popped using ets:first().
        Agenda = ets:new(?AGENDA, [ordered_set, {keypos, #?AGENDA.key}]),

        % The used table is in no order and is keyed on vertex set.
        Used = ets:new(?USED, [set, {keypos, #?USED.vertexSet}])},

  % Add agenda items for each notification op.
  {ok, Records} = prog_srv:get_deep_contents(FolderRef),
  {Ns, Gens, Cons} = op_groups(Records),
  lists:foreach(fun(N) ->
                     add_op_agenda(N, ?UNDEFINED, Db)
                end, Ns),

  % Process the agenda until empty.
  process_agenda(Db, {Gens, Cons}),

  % Clean up the ETS tables we used.
  ets:delete(Agenda),

  % Return the ETS table of vertices, the updated digraph and the list of
  % consumer operations.
  {Graph, Used, Cons}.

%% @doc Isolates and groups operation records from the supplied list of records
%% which may include field and folder records.
%% The op ref lists in the returned tuple are as follows:
%% {N, IRR+RR, IRR+OO}
%% The N ops are sources used to initialize the agenda.
%% The IRR+RR ops generate new agenda items.
%% The IRR+OO ops are consumers (i.e. sinks).
%% @spec op_groups(list()) -> {list(), list(), list()}
op_groups(Records) ->
  lists:foldl(fun(Record, {Ns, Generators, Consumers} = Groups) ->
                 case Record of
                   #?OP{opType = ?OP_TYPE_N} ->
                     {[Record | Ns], Generators, Consumers};
                   #?OP{opType = ?OP_TYPE_IRR} ->
                     {Ns, [Record|Generators], [Record|Consumers]};
                   #?OP{opType = ?OP_TYPE_RR} ->
                     {Ns, [Record|Generators], Consumers};
                   #?OP{opType = ?OP_TYPE_OO} ->
                     {Ns, Generators, [Record|Consumers]};
                   _Other -> Groups
                 end
              end,
              {[], [], []}, Records).

%% @doc Adds the output sets present on the supplied op to the agenda.
%% #1 adds vertex agenda items.
%% @spec add_op_agenda(#op{}, set() | [], db()) -> true
add_op_agenda(#?OP{id = Id,
                   opType = OpType,
                   outputs = Outputs},
              _InputVertex, Db)
  when OpType =:= ?OP_TYPE_N orelse OpType =:= ?OP_TYPE_IRR ->
  nr_set_dict:fold(
    fun(OutputName, Output, ?NULL_ACC) ->
         Refs = nr_set:ref_set(Output),
         add_agenda_item(Db, #?AGENDA{type = ?VERTEX,
                                      opRef = {?OP, Id},
                                      outputName = OutputName,
                                      vertexSet = Refs}),
         ?NULL_ACC
    end,
    ?NULL_ACC, Outputs),
  ok;

%% #2 adds edge agenda items.
add_op_agenda(#?OP{id = Id,
                   opType = OpType,
                   outputs = Outputs},
              InputVertex, Db)
  when OpType =:= ?OP_TYPE_RR ->
  nr_set_dict:fold(
    fun(OutputName, Output, ?NULL_ACC) ->
         Refs = nr_set:ref_set(Output),
         Item = #?AGENDA{type = ?EDGE,
                         opRef = {?OP, Id},
                         inputVertex = InputVertex,
                         outputName = OutputName,
                         vertexSet = union(Db, InputVertex, Refs)},
         add_agenda_item(Db, Item),
         ?NULL_ACC
    end,
    ?NULL_ACC, Outputs),
  ok.

%% @doc Adds an agenda item to the db.
%% @spec add_agenda_item(db(), #graph_agenda{}) -> true
add_agenda_item({_Digraph, Agenda, _Used}, #?AGENDA{} = Item) ->
  ets:insert(Agenda, Item).

%% @doc Returns the next agenda item from the DB, removing it from the agenda.
%% @spec pop_agenda_item(db()) -> agenda_empty | #graph_agenda{}
pop_agenda_item({_Digraph, Agenda, _Used}) ->
  case ets:first(Agenda) of
    '$end_of_table' ->
      ?AGENDA_EMPTY;
    Key ->
      [Item] = ets:lookup(Agenda, Key),
      ets:delete(Agenda, Key),
      Item
  end.

%% @doc Returns the union of the input vertex (if defined) and the output set.
%% @spec union(db(), vertex(), set()) -> void()
union(Db, InputVertex, OutputSet) ->
  case InputVertex of
    ?UNDEFINED -> OutputSet;
    InputVertex -> sets:union(get_vertex_set(Db, InputVertex), OutputSet)
  end.

%% @doc Returns the fieldset associated with this vertex.
%% @spec get_vertex_set(db(), vertex()) -> set()
get_vertex_set({Digraph, _Agenda, _Used}, Vertex) ->
  {Vertex, #?VERTEX_LABEL{vertexSet = VertexSet}} =
    digraph:vertex(Digraph, Vertex),
  VertexSet.

%% @doc Stores the vertex set/vertex entry in the dictionary of
%% used vertex states.
%% @spec store_vertex(ets(), set(), vertex()) -> ok
store_vertex(Table, VertexSet, Vertex) ->
  OrdSet = ordsets:from_list(sets:to_list(VertexSet)),
  ets:insert(Table, #?USED{vertexSet = OrdSet,
                           vertex = Vertex}).

%% @doc Returns vertex and label associated with `VertexSet'..
%% @spec get_vertex(ets(), set()) -> vertex()
get_vertex(Table, Set) ->
  OrdSet = ordsets:from_list(sets:to_list(Set)),
  [#?USED{vertex = Vertex}] = ets:lookup(Table, OrdSet),
  Vertex.

%% @doc Returns vertex if `VertexSet' is already represented in the used table,
%% false otherwise.
%% @spec existing_vertex(ets(), set()) -> vertex() | false
existing_vertex(Table, Set) ->
  OrdSet = ordsets:from_list(sets:to_list(Set)),
  case ets:lookup(Table, OrdSet) of
    [] -> false;
    [#?USED{vertex = Vertex}] ->
      Vertex
  end.

%% @doc Processes each agenda item in turn until empty.
%% @spec process_agenda(db(), op_groups()) -> ok
process_agenda(Db, Ops) ->
  case pop_agenda_item(Db) of
    ?AGENDA_EMPTY ->
      ok;
    Item ->
      process_item(Item, Db, Ops),
      process_agenda(Db, Ops)
    end.

%% @doc Processes a single agenda item, creating or updating a vertex
%% and/or creating a new edge depending on the agenda item type.
%% @spec process_item(#graph_agenda{}, db(), {list(), list()}) -> void()
process_item(#?AGENDA{type =Type,
                      opRef = OpRef,
                      inputVertex = InputVertex,
                      outputName = OutputName,
                      vertexSet = VertexSet},
             {Digraph, _Agenda, Used} = Db, Ops) ->

  % Determine agenda item type and whether it represents a new vertex, and
  % process accordingly.
  case {Type, existing_vertex(Used, VertexSet)} of
    {?VERTEX, false} ->
      Vertex = new_vertex(VertexSet, Db, Ops),
      update_label(Vertex, OpRef, OutputName, Digraph);
    {?EDGE, false} ->
      Vertex = new_vertex(VertexSet, Db, Ops),
      new_edge(InputVertex, Vertex, OpRef, OutputName, Digraph);
    {?VERTEX, Vertex} ->
      update_label(Vertex, OpRef, OutputName, Digraph);
    {?EDGE, Vertex} ->
      new_edge(InputVertex, Vertex, OpRef, OutputName, Digraph)
  end.

%% @doc Creates a new edge.
%% @spec new_edge(vertex(), vertex(), ref(), string(), digraph()) -> void()
new_edge(From, To, OpRef, OutputName, Digraph) ->
  ELabel = #?EDGE_LABEL{generator = OpRef,
                        outputName = OutputName},
  digraph:add_edge(Digraph, From, To, ELabel).

%% @doc Creates a new vertex from an agenda item, and traverses the generator
%% ops to create new agenda items arising from the new vertex.
%% @spec new_vertex(set(), db(), {list(), list()}) -> void()
new_vertex(VertexSet, Db, {Gens, Cons}) ->

  % Create the new vertex.
  {Digraph, _Agenda, Used} = Db,
  Vertex = digraph:add_vertex(Digraph),

  % Update the used table to show the new  vertex exists.
  store_vertex(Used, VertexSet, Vertex),

  % Label the vertex with IRR+OO consumer op refs that are satisfied by
  % the new vertex.
  Satisfies = [{?OP, Id} ||
               #?OP{id = Id} <- lists:filter(
                  fun(#?OP{mask = Mask,
                           input = Input}) ->
                       sets:is_disjoint(nr_set:ref_set(Mask), VertexSet) andalso
                         sets:is_subset(nr_set:ref_set(Input), VertexSet)
                  end, Cons)],
  digraph:add_vertex(Digraph, Vertex,
                     #?VERTEX_LABEL{vertexSet = VertexSet,
                                    satisfies = Satisfies}),

  % Get generator IRR+RR ops that can execute off of the new vertex. These are
  % used to create new agenda items.
  Generators =
    lists:filter(fun(#?OP{mask = Mask,
                          input = Input,
                          outputs = Outputs,
                          opType = OpType}) ->
                      MaskSet = nr_set:ref_set(Mask),
                      InputSet = nr_set:ref_set(Input),
                      case OpType of
                        ?OP_TYPE_RR ->
                          OutputUnion = nr_set_dict:ref_union_set(Outputs),
                          sets:is_disjoint(MaskSet, VertexSet) andalso
                            sets:is_subset(InputSet, VertexSet) andalso
                            sets:is_disjoint(OutputUnion, VertexSet);
                        ?OP_TYPE_IRR ->
                          sets:is_disjoint(MaskSet, VertexSet) andalso
                            sets:is_subset(InputSet, VertexSet)
                        end
                 end, Gens),

  % Fold all relevant ops over the new vertex. This may cause new agenda
  % items (vertex and/or edge types) to be generated.
  lists:foreach(fun(Op) ->
                     add_op_agenda(Op, Vertex, Db)
                end,
                Generators),

  % Return the new vertex.
  Vertex.

%% @doc Updates the label on the supplied vertex.
%% @spec update_label(vertex(), ref(), string(), digraph()) -> void()
update_label(Vertex, OpRef, OutputName, Digraph) ->
  {Vertex, #?VERTEX_LABEL{producedBy = Old} = VLabel} =
    digraph:vertex(Digraph, Vertex),
  digraph:add_vertex(Digraph, Vertex,
    VLabel#?VERTEX_LABEL{producedBy = [{OpRef, OutputName} | Old]}).
